\chapter{A little bit conclusion}

По лекции от 29 сентября 2011 года

\subsection{Подведем маленький итог}

Все рассмотренные нами задачи на ящиках, урнах и прочих контейнерах имееют общую природу - мы подсчитываем количество отображений из одного множества в другое, удолетворяющих определенным условиям.

Пусть имеются два множества $X$ и $Y$, причем $\left|X\right| = k$ и $\left|Y\right|=n$, и имеется отображение: $f : X \rightarrow Y$. Необходимо подсчитать количество таких отображений:

\begin{itemize}
\item Число всех функций равно $n^k$

\item Число инъектвных функций $\left(n\right)_k$

\item Число биективных функций $n!$

\item Число сюрективных функций $\hat S \left(k,n\right)$
\end{itemize}

Все эти задачи сводятся к задачам распределения различных предметов по различным ящикам, теперь рассмотрим распределение одинаковых предметов по различным ящикам, т. е. количество целочисленных решений уравнения $a_1 + a_2 + ... + a_n = k$ при различных ограничениях:

\begin{itemize}
\item Пусть $a_i \ge 0$, тогда количество решений $\left(\binom{n}{k}\right)$

\item Пусть $a_i \in \{0,1\}$, тогда количество решений $\binom{n}{k}$

\item Пусть $a_i = 1$, тогда $1$ (ну эт шутка на самом деле)

\item Пусть $a_i \ge 1$, тогда $\binom{k-1}{n-1}$
\end{itemize}

\subsection{Вернемся к делу}

$\hat S \left(n, k\right)$ - количество распределений $n$ различных предметов по $k$ различным ящикам, причем так чтобы в каждый ящик попал хотябы один предмет, т. е. важен порядок этих ящиков, а если нам не важен порядок, то число таких разделений $S \left(n,k\right)$, а следовательно:
\[
	S \left(n,k\right) k! = \hat S \left(n,k\right) \Leftrightarrow S \left(n, k\right) = \frac{1}{k!} \hat S \left(n,k\right)
\]

Для чисел Стирлинга не трудно проверить утверждения:
\[
	\begin{split}
	& S \left(n,n\right) = 1 \\
	& S \left(n,1\right) = 1
	\end{split}
\]

В дальнейшем нам они понадобятся, но пока рассмотрим пример - пусть $X = \{1,2,3,4\}$, рассмотрим возможные разделения этого множества без учета порядка:
\begin{itemize}
\item $k=1$: $\{\{\{1,2,3,4\}\}\}$

\item $k=4$: $\{\{\{1\},\{2\},\{3\},\{4\}\}\}$

\item $k=2$: \[
	\begin{split}
		& \{\{\{1,2,3\},\{4\}\},\{\{1,2,4\},\{3\}\},\{\{1,3,4\},\{2\}\},\\
		& \{\{2,3,4\},\{1\}\},\{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\\
		& \{\{1,4\},\{2,3\}\}\}
	\end{split}
	\]

\item $k=3$: \[
	\begin{split}
		& \{\{\{1,2\},\{3\},\{4\}\},\{\{1,3\},\{2\},\{4\}\},\\
		& \{\{1,4\},\{2\},\{3\}\},\{\{2,3\},\{1\},\{4\}\},\\
		& \{\{2,4\},\{1\},\{3\}\},\{\{3,4\},\{1\},\{2\}\}\}
	\end{split}
	\]
\end{itemize}

Глядя на пример выведем пару формул, начнем с числа $S\left(n,2\right)$, количество всех отображений из множества $X$ мощностью $n$ в множество мощностью $2$ равно $2^n$, из них очевидно два нам не удовлетворяют ($\{X, \empty\}$ и $\{\empty, X\}$), кроме того, так как мы не хотим учитывать порядок поделим все на 2, в итоге:
\[
	S \left( n,2\right) = 2^{n-1}-1
\]

Искать каждый раз значение числа Стирлинга подобным образом очень тяжко, да и ко всему прочему не так все и просто будет, поэтому выведем реккурентную формулу для чисел Стирлинга. Выделим в множестве 1 элемент, все разбиения относительно этого элемента можно разбить на два блока:
\begin{itemize}
\item $\Sigma^{\left(1\right)}$ - разбиения, в которых элемент 1 присутсвует в качетсве самостоятельного множества $\{1\}$

\item $\Sigma^{\left(2\right)}$ - разбиения, в которые элемент 1 присутсвует внутри некоторого другого множества (т. е. те в которых нет $\{1\}$)
\end{itemize}

\[
	\begin{split}
		& \left|\Sigma^{\left(1\right)}\right| = S \left(n-1, k-1\right) \\
		& \left|\Sigma^{\left(2\right)}\right| = k S \left(n-1, k\right)
	\end{split}
\]

Очеидность первого равенства не вызывает сомнений, второе не на много сложнее - если посчитать множество разбиений исходного множества без элемента 1, то их число очевидно $S \left(n-1,k\right)$, добавив в любое множество элемент 1 получаем требуемое, так как в каждое разбиение состоит из $k$ блоков, то, соответственно, и способов добавить 1 ровно $k$
